package com.mashibing.class12;

/**
 * 最大距离的可能性
 * 1) X左树的最大距离 .
 * 2) X右树的最大距离 .
 * 3) X左树与X最远(左树高度) + X右树与X最远(右树高度) + 1 .
 */
public class Code06_MaxDistance {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static int maxDistance(Node head){
        return process(head).maxDisance;
    }

    public static class Info{
        public int maxDisance; // 最大距离
        public int height;// 高度

        public Info(int maxDisance, int height) {
            this.maxDisance = maxDisance;
            this.height = height;
        }
    }

    public static Info process(Node node){
        if (node == null){
            return new Info(0,0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDisance;
        int p2 = rightInfo.maxDisance;
        int p3 = leftInfo.height + rightInfo.height +1;
        int maxDistance = Math.max(Math.max(p1,p2),p3);
        return new Info(maxDistance,height);
    }
}
